Red-Black Tree

#DataStructure #DataStructure-Tree #DataStructure-Binary_Tree #DataStructure-BST #DataStructure-Red_Black_Tree

이진 트리(Binary Tree) 일부 복붙

1. Red-Black Tree

이것은 이름에 특징이 나와있다. 노드의 색이 빨강 혹은 검정으로 되어있는 이진 균형 트리를 말한다.
레드-블랙 트리는 노드를 빨강과 검정으로 구분하는 것을 통해서 균형을 유지한다. 때문에 이 트리의 정체성을 지켜주기 위한 몇가지 색상 규칙이 있다.

  1. 루트 노드는 항상 검은색이다.
  2. 트리의 모든 노드는 검은색 혹은 빨강색 중 하나의 색이여야 한다.
  3. 리프 노드는 모두 검은색이고, 데이터 값을 갖지 않는다.
  4. 빨간색 노드의 자식 노드는 검은색이다.
    • (검은색 노드의 자식 노드는 검은색일 수 있다.)
    • (빨간색 노드의 자식이 빨간색 노드일 수 없다. No Double Red)
  5. 루트 노드에서 리프 노드까지의 경로에 있는 블랙 노드의 수는 모두 같다.

레드-블랙 트리는 색상의 조건이 깨지는 경우 리밸런싱을 하는데, Restructuring인 회전이 아닌 Recoloring만 진행하는 경우도 있어 회전 수행이 AVL보다 적다. 때문에 삽입, 삭제에는 효율적이지만 탐색에는 AVL보다는 비효율적이다.

2. Self-Balancing

Red-Black Tree의 리밸런싱은 No Double Red가 위반되었을 때 진행된다.
이 때 AVLTree와 마찬가지로 리밸런싱이 Restructuring일 수도 있지만, 그렇지 않고 Recoloring이 진행될 수도 있다. (균형을 맞춘다는 의미의 리밸런싱은 아님)

설명과 구현은 균형 이진 트리에 대해 자세히 알아보기!(비선형 자료구조), dnrwhddk1.log, WOOK JONG KIM 포스트에 잘 정리되어 있으니 이것을 참고하면 될 것 같다.